package Year22_Month05.day23;

import java.util.Arrays;

public class 插入排序 {
    public static void insertSort(int[] arr) {
        for(int i = 1;i < arr.length;i++){
            int key = arr[i];//定义当前需要比较的元素
            //然后要和i下标之前的元素进行比较，如果说元素比当前元素大，那么就往后挪一位
            int end = i - 1;
            while(end >= 0 && key < arr[end]){
                arr[end + 1] = arr[end];
                end--;
            }
            //这一步走完了之后，当前end下标所对应的值肯定是小于key的，所以对其后一位进行赋值
            arr[end + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,2,8,6,9,1,3,5,0,7};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
